Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій і комп’ютерної інженерії Кафедра комп’ютерних наук   Лабораторна робота №3З дисципліни: Теорія алгоритмів Тема: «Аналіз алгоритму сортування методом злиття»  Вінниця, 2017 Аналіз алгоритму сортування методом злиття Мета: навчитись аналізувати алгоритми на прикладі алгоритму сортування методом злиття Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй». В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової. Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності Приклад реалізації на Java public class Solution{ public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Введіть кількість елементів масива"); int num = Integer.parseInt(reader.readLine()); int arr[] = new int[num]; System.out.println("Рaндомний массив:"); for(int i = 0; i < arr.length; i++) {//элементу массива присваивается случайное число от 0 до 99 arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + " "); } long timeout= System.currentTimeMillis(); mergesort(arr); timeout = System.currentTimeMillis() - timeout; System.out.println("Час затрачений на виконання сортування = "+ timeout+ "мc"); } public static void mergesort(int[] arr) { System.out.println("\nВідсортований масив:"); int n = arr.length; boolean c = true; int i = 0; int i1 = 0; int i2 = 0; int n1 = 0; int n2 = 0; int[] barr = new int[n]; int mergelen = 0; barr = new int[n]; mergelen = 1; while (mergelen < n) { if (c) { i = 0; while (i + mergelen <= n) { i1 = i + 1; i2 = i + mergelen + 1; n1 = i + mergelen; n2 = i + 2 * mergelen; if (n2 > n) { n2 = n; } while (i1 <= n1 | i2 <= n2) { if (i1 > n1) { while (i2 <= n2) { i = i + 1; barr[i - 1] = arr[i2 - 1]; i2 = i2 + 1; } } else { if (i2 > n2) { while (i1 <= n1) { i = i + 1; barr[i - 1] = arr[i1 - 1]; i1 = i1 + 1; } } else { if (arr[i1 - 1] > arr[i2...